package com.gjy.ds.sort_search;

/**
 * @author 宫静雨
 * @version 1.0
 * @since 2023-06-20 11:40:28
 */
public class Sort9 {

    public void quick(int[] arr, int left, int right) {
        int l = left;
        int r = right;
        int mid = arr[(left + right) / 2];
        while (l < r) {
            while (arr[l] < mid) {
                l += 1;
            }
            while (arr[r] > mid) {
                r -= 1;
            }
            if (l >= r) {
                break;
            }
            swap(arr, l, r);

            if (arr[l] == mid) {
                r -= 1;
            }
            if (arr[r] == mid) {
                l += 1;
            }
        }
        if (l == r) {
            l += 1;
            r -= 1;
        }
        if (left < r) {
            quick(arr, left, r);
        }
        if (right > l) {
            quick(arr, l, right);
        }
    }

    public void shell1(int[] arr) {
        for (int gap = arr.length; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]) {
                        swap(arr, j, j + gap);
                    }
                }
            }
        }
    }

    public void insert(int[] arr) {
        int val;
        int index;
        for (int i = 1; i < arr.length; i++) {
            val = arr[i];
            index = i - 1;
            while (index >= 0 && val < arr[index]) {
                arr[index + 1] = arr[index];
                index--;
            }
            if (index + 1 != i) {
                arr[index + 1] = val;
            }
        }
    }

    public void select2(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = arr[i];
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                int current = arr[j];
                if (min > current) {
                    minIndex = j;
                    min = current;
                }
            }
            if (minIndex != i) {
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
    }

    public void select(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int minIndex = i;
            int min = array[i];
            for (int j = i + 1; j < array.length; j++) {
                if (min > array[j]) {
                    min = array[j];
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                array[minIndex] = array[i];
                array[i] = min;
            }
        }
    }

    public void bubble(int[] array) {
        boolean flag = false;
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    flag = true;
                    swap(array, j, j + 1);
                }
            }
            if (!flag) {
                break;
            } else {
                flag = false;
            }
        }
    }

    public void swap(int[] array, int i, int j) {
        array[i] = array[i] ^ array[j];
        array[j] = array[i] ^ array[j];
        array[i] = array[i] ^ array[j];
    }

}
